#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	int largestRectangleArea(vector<int>& heights)
	{
		int length = heights.size();
		if (length == 0) return 0;
		if (length == 1) return heights[0];
		int res = 0;

		stack<int> aux; aux.emplace(0);
		heights.emplace_back(0); heights.insert(heights.begin(), 0);
		for (int i = 1, len = length + 2; i < len; i++) {
			while (heights[aux.top()] > heights[i]) {
				int curMax = heights[aux.top()]; aux.pop();
				int width = i - 1 - aux.top();
				res = max(res, width * curMax);
			}
			aux.emplace(i);
		}
		return res;
	}
};

int main()
{
	return 0;
}
